/**
 * 自顶向下的排序算法
 * 就是把数组元素不断的二分，直到子数组的元素个数为一个，
 * 因为这个时候子数组必定是已有序的，
 * 然后将两个有序的序列合并成一个新的有序的序列，
 * 两个新的有序序列又可以合并成另一个新的有序序列，
 * 以此类推，直到合并成一个有序的数组。
 * @author dc
 * @Classname MergeSort
 * @Date 2020/1/4 12:51
 */
public class MergeSortUb extends BaseSort{
    /**归并所需的辅助数组*/
    private static Comparable[] aux;

    /**
     * 此方法为辅助函数,主要目的用于创建辅助数组,提高效率
     * @param a
     */
    public static void sort(Comparable[] a) {
        //一次性分配空间
        aux = new Comparable[a.length];
        sort(a,0,a.length-1);
    }

    /**
     * 归并排序的主方法
     * 将数组a[lo...hi]排序
     * @param a 需要归并排序的数组
     * @param lo 数组第一个元素位置
     * @param hi 数组最后一个元素位置
     */
    private static void sort(Comparable[] a, int lo, int hi) {
        //划分到最小规模,即为单个元素时进行比较归并
        if(hi<=lo){
            return;
        }
        //当数据较大超过int的范围时,会溢出,因此使用此方法求中值
        int mid = lo + (hi-lo)/2;
        //将左半边数组a[lo...mid]进行排序
        sort(a,lo,mid);
        //将数组右半边a[mid+1...hi]进行排序
        sort(a,mid+1,hi);
        //排完之后将两个有序数组进行归并
        merge(a,lo,mid,hi);
    }

    /**
     * 原地归并抽象方法
     * 用于将两个不同的有序数组归并到第三个数组中
     * @param a 需要归并进入的原数组
     * @param lo   原数组第一个
     * @param mid  原数组中间
     * @param hi   原数组最后一个
     */
    public static void merge(Comparable[] a,int lo,int mid,int hi){
        //将a[lo..mid]和a[mid+1...hi]两个拆分后有序数组进行归并
        int i=lo;
        int j=mid+1;
        //将原数组a[lo..hi]复制到aux[lo...hi]数组中
        for(int k=lo;k<=hi;k++){
            aux[k]=a[k];
        }
        for(int k=lo;k<=hi;k++){
            //将a[lo..mid]和a[mid+1...hi]归并回到a[lo...hi]中
            if(i>mid){
                //左半边数组a[lo...mid]取尽,直接取右边数组
                a[k]=aux[j++];
            }else if(j>hi){
                //右半边数组a[mid+1...hi]取尽,依次取左边数组
                a[k]=aux[i++];
            }else if(less(aux[j],aux[i])){
                //如果左边数组取出的元素小于右边取出的元素
                //则将右边数组的元素归并回原数组,并且指针后移
                a[k]=aux[j++];
            }else{
                //反之将左边数组的元素归并回原数组,并且指针后移
                a[k]=aux[i++];
            }
        }
    }
}
